Từ năm 1940 đến năm 1943, Nguyễn Hữu Khiếu bị thực dân Pháp giam tại nhà lao Đăk Mil (huyện Đắk Mil, tỉnh Đắc Nông).

Tháng 3 năm 1945 ông là Ủy viên Xứ ủy Ai Lao tại Lào.

Trong kháng chiến chống Pháp, ông làm Phó Bí thư Liên khu ủy Liên khu 4 kiêm Giám đốc Công an Liên khu IV.

Với cương vị Giám đốc Công an khu 4 Nguyễn Hữu Khiếu là người rất thương đồng đội, tin tưởng đồng đội. Ông rất hiểu và biết "dùng" cán bộ của mình để bố trí đúng người đúng việc vì lực lượng Công an Khu 4 lúc bấy giờ được ông tập hợp rất nhiều người ở nhiều ngành nghề tham gia, đại bộ phận là nhân viên còn rất trẻ. Ông biết "cài cắm" ai vào nhiệm vụ nào để hoàn thành nhiệm vụ tốt nhất. Trong lúc bộn bề công việc mà vẫn đạp xe hơn năm chục cây số, thay mặt nhà trai đi hỏi vợ cho cán bộ của mình. Anh em ốm đau, ông dặn dò hậu cần phải chăm lo tốt bữa ăn cho anh em.

Ông đã xây dựng lực lượng Công an Khu 4 trong sạch, vững mạnh, không có một cán bộ nào phạm sai lầm nghiêm trọng. Đặc biệt, ông rất quan tâm đào tạo cán bộ kế cận. Trong các cuộc họp giao ban của Ban giám đốc, ông đều mời lãnh đạo phòng, ban tới dự, cùng nghe chủ trương, cùng bàn biện pháp, lắng nghe ý kiến của anh em. Vì vậy, không khó khăn khi bố trí cán bộ thay thế.Ông dặn dò của nhân viên dưới quyền: "Sự rèn luyện của người chiến sĩ cũng như rèn một cái dùi, lấy cái dùi ấy đâm vào vách đất, thì đừng vội tự mãn - phải rèn cho đến khi đem nó đâm vào tường vôi mà không bị quằn mũi".

Ông là người có tầm nhìn chiến lược, dự đoán được ngày hòa bình lập lại và trong khoảng thời gian ngắn ngủi đó tích cực, tranh thủ chuẩn bị lực lượng tình báo để tung vào hàng ngũ kẻ thù bằng nhiều con đường, chuẩn bị cho cuộc đấu tranh lâu dài. Nhiều cán bộ tình báo đã ở vị trí lãnh đạo, giữ trọng trách trong bộ máy của địch, biết cách dùng địch để địch mắc mưu ta, khiến chúng không lường được.